In 2012, inspired by developments in group theory and complexity, Jockuschand Schupp introduced generic computability, capturing the idea that analgorithm might work correctly except for a vanishing fraction of cases.However, we observe that their definition of a negligible set is not computablyinvariant (and thus not well-defined on the 1-degrees), resulting in somefailures of intuition and a break with standard expectations in computabilitytheory. To strengthen their approach, we introduce a new notion of intrinsicasymptotic density, with rich relations to both randomness and classicalcomputability theory. We then apply these ideas to propose alternativefoundations for further development in (intrinsic) generic computability. Toward these goals, we classify intrinsic density 0 as a new immunityproperty, specifying its position in the standard hierarchy from immune tocohesive for both general and $\Delta^0_2$ sets, and identify intrinsic density$\frac{1}{2}$ as the stochasticity corresponding to permutation randomness. Wealso prove that Rice's Theorem extends to all intrinsic variations of genericcomputability, demonstrating in particular that no such notion considers$\emptyset'$ to be "computable".
展开▼
